package Algorithm.LinkedListProblem;

/**
 * @Author cj
 * @Date 2022/1/9 9:57
 */
public class selectSort {

    static class Node {
        public int value;
        public Node next;

        public Node(int val) {
            this.value = val;
        }
    }

    public static Node selectSort1(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node tail = null; // 排序后的末尾
        Node small = null; // 未排序中最小节点
        Node smallPre = null; // 未排序中最小节点前一个节点
        Node cur = head;
        while (cur != null) {
            small = cur;
            smallPre = getSmallestPre(cur);
            if (smallPre != null) { // 删除small节点
                small = smallPre.next;
                smallPre.next = small.next;
            }
            cur = cur == small ? cur.next : cur;
            // 拼接排序节点
            if (tail == null) {
                head = small;
            } else {
                tail.next = small;
            }
            tail = small;
        }
        return head;
    }

    private static Node getSmallestPre(Node head) {
        Node cur = head.next;
        Node pre = head;
        Node small = head;
        Node smallPre = null;
        while (cur != null) {
            if (cur.value < small.value) {
                small = cur;
                smallPre = pre;
            }
            pre = cur;
            cur = cur.next;
        }
        return smallPre;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(1);
        head.next.next.next = new Node(5);
        head.next.next.next.next = new Node(4);
        Node a = selectSort1(head);
        while (a != null) {
            System.out.println(a.value);
            a = a.next;
        }
    }

}
